#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void sieve_of_eratosthenes(int n) {
    char *is_prime = (char *)malloc((n + 1) * sizeof(char));
    if (is_prime == NULL) {
        printf("Memory allocation failed\n");
        return;
	} 
    for (int i = 0; i <= n; i++) {
        is_prime[i] = 1;
    }
    is_prime[0] = is_prime[1] = 0;
    for (int current = 2; current <= sqrt(n); current++) {
        if (is_prime[current]) {
            for (int multiple = current * current; multiple <= n; multiple += current) {
                is_prime[multiple] = 0;
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            printf("%d\n", i);
        }
    }
    free(is_prime);
}
int main() {
    int n;
    scanf("%d", &n);
    sieve_of_eratosthenes(n);
    return 0;
}
    